package offer.day20;

import java.util.Arrays;

public class No33VerifySequenceOfBST {
    /*
     * 面试题33：二叉搜索树的后序遍历序列
     * 题目:输入一个整型数组，判断该数组是不是某二叉搜索树的后序遍历结果。
     * 如果是则返回true,否则返回false.假如输入的数组的任意两个数组都各不相同
     * 例如：输入数组{5，7，6，9，11，10，8}，则返回true，
     * 因为这个整数序列是8->(left)6  8->(right)10 二叉搜索树的后序遍历结果。
     * 			   6->(left)5  6->(right)7
     * 			   10->(left)9  10->(right)11
     * 如果输入的数组是{7，4，6，5}，则由于没有哪一棵二叉搜索树的后序遍历结果是这个序列，因此返回false
     *
     * 思路：二叉搜索树是一个排序的二叉树，左边都比根节点小，右边都比根节点大；
     * 所以除去最后的根节点之后，左边的元素都小于根，右边的元素都大于根
     * 1-> 首先 根据这个特性可以首先从左到右依次判断，第一个大于根节点的值，那么从最左边到该点的值就是比根节点小的了。
     *     判断根节点这一层次是否符合二叉搜索树的后序遍历标准，若有不满足的返回false
     *     （右侧应该大于根结点的部分，却存在小于根节点的元素）
     * 2-> 然后再判断是否有左子树，若有则判断一下左子树大体上是否符合二叉搜索树的后序遍历标准
     * 3-> 最后判断是否有右子树，若有则判断右子树是否符合二叉搜索树的后序遍历结果
     * 最后将其整合left && right
     *
     * */
    public static void main(String[] args) {
        No33VerifySequenceOfBST v = new No33VerifySequenceOfBST();


        int[] array = {5, 7, 6, 9, 11, 10, 8};
        if (v.VerifySequenceOfBST(array))
            System.out.println("这个整数序列是一个二叉搜索树的后序遍历结果！！");
        else
            System.out.println("这个整型序列不是任何一个二叉搜索树的后序遍历结果！！！！");
    }

    private boolean VerifySequenceOfBST(int[] array) {
        int length = array.length;
        if (length == 0) return false;
        int root = array[length - 1];
        //寻找左右子树
        int i = 0;
        for (; i < length - 1; i++) {
            if (array[i] > root) {
                break;
            }
        }
        //验证左右子树
        int j = i;
        for (; j < length - 1; j++) {
            if (array[j] < root) {
                return false;
            }
        }
        if (0 < i && i < length - 1) {
            VerifySequenceOfBST(Arrays.copyOfRange(array, 0, i - 1));
            VerifySequenceOfBST(Arrays.copyOfRange(array, i, length - 1));
        }
        return true;
    }
}
